package offer.day36;

import java.util.Stack;

public class No68Third_FetLowestCommonAncestorTree {
    /*
     * 面试题68：最低公共祖先  *********难！！！！！
     * 给出树中的两个节点，求这两个节点的最低公共祖先
     * 题目三：树是普通树，没有指向父节点的指针
     *
     * 思路：用栈的方式来实现类似于指向父节点指针的功能，
     * 获取node节点的路径时间复杂度为O(n)，所以总的时间复杂度O(n),空间复杂度O(logn)
     *
     * */
    public static void main(String[] args) {
        No68Third_FetLowestCommonAncestorTree p = new No68Third_FetLowestCommonAncestorTree();

        TreeNode1 root1 = new TreeNode1(5);
        TreeNode1 one = new TreeNode1(3);
        TreeNode1 two = new TreeNode1(7);
        TreeNode1 three = new TreeNode1(2);
        TreeNode1 four = new TreeNode1(4);
        TreeNode1 five = new TreeNode1(6);
        TreeNode1 six = new TreeNode1(8);

        root1.one = one;
        root1.two = two;
        root1.three = three;
        one.one = four;
        one.two = five;
        one.three = null;
        two.one = null;
        two.two = null;
        two.three = null;
        three.one = null;
        three.two = null;
        three.three = null;
        four.one = six;
        four.two = null;
        four.three = null;
        five.one = null;
        five.two = null;
        five.three = null;
        six.one = null;
        six.two = null;
        six.three = null;

        System.out.println("两个节点的最低公共祖先：" + p.GetLowestCommonAncestor(root1, six, four));
    }

    private TreeNode1 GetLowestCommonAncestor(TreeNode1 root1, TreeNode1 node1, TreeNode1 node2) {
        if (root1 == null || node1 == null || node2 == null) return null;
        Stack<TreeNode1> stack1 = new Stack<>();
        Stack<TreeNode1> stack2 = new Stack<>();
        boolean flag1 = findTheDepthOfTheNode(root1, node1, stack1);
        boolean flag2 = findTheDepthOfTheNode(root1, node2, stack2);
        if (!flag1 || !flag2) return null;
        int depth1=stack1.size();
        int depth2=stack2.size();
        int depth=Math.abs(depth1-depth2);
        if(depth1>depth2){
            while(depth>0){
                stack1.pop();
                depth--;
            }
        }else if(depth1<depth2){
            while(depth>0){
                stack2.pop();
                depth--;
            }
        }
        TreeNode1 p=stack1.peek();
        TreeNode1 q=stack2.peek();
        if(p==q){
            stack1.pop();
            return stack1.pop();
        }else{
            while(p!=q){
                p=stack1.pop();
                q=stack2.pop();
            }
            return q;
        }

    }

    private boolean findTheDepthOfTheNode(TreeNode1 root1, TreeNode1 node, Stack<TreeNode1> stack) {
        stack.push(root1);
        if (node == root1) return true;
        boolean flag = false;
        if (root1.one != null) {
            flag = findTheDepthOfTheNode(root1.one, node, stack);
        }
        if (!flag && root1.two != null) {
            flag = findTheDepthOfTheNode(root1.two, node, stack);
        }
        if (!flag && root1.three != null) {
            flag = findTheDepthOfTheNode(root1.three, node, stack);
        }
        if (!flag) {
            stack.pop();
        }
        return flag;
    }
}
